class Course:
    def __init__(self, name, teacher, possible_rooms):
        self.name = name
        self.teacher = teacher
        self.possible_rooms = possible_rooms
        self.assigned_room = None
        self.assigned_time = None

class Room:
    def __init__(self, name):
        self.name = name

class TimeSlot:
    def __init__(self, time):
        self.time = time

def is_valid_assignment(course, room, time, courses, rooms, times):
    # 检查教室在同一时间段内是否已经分配了其他课程
    for c in courses:
        if c.assigned_room == room and c.assigned_time == time:
            return False
    # 检查教师在同一时间段内是否已经教授了其他课程
    for c in courses:
        if c.teacher == course.teacher and c.assigned_time == time:
            return False
    return True

def backtrack(courses, rooms, times, index=0):
    if index == len(courses):
        return True  # 所有课程都已成功分配

    course = courses[index]
    for room in course.possible_rooms:
        for time in times:
            if is_valid_assignment(course, room, time, courses, rooms, times):
                course.assigned_room = room
                course.assigned_time = time
                if backtrack(courses, rooms, times, index + 1):
                    return True
                # 回溯
                course.assigned_room = None
                course.assigned_time = None
    return False

def print_schedule(courses):
    for course in courses:
        if course.assigned_room and course.assigned_time:
            print(f"课程: {course.name}, 教师: {course.teacher}, 教室: {course.assigned_room.name}, 时间: {course.assigned_time.time}")
        else:
            print(f"课程: {course.name} 未成功分配教室和时间")

# 示例数据
courses = [
    Course("数学", "张老师", [Room("101"), Room("102")]),
    Course("语文", "李老师", [Room("101"), Room("103")]),
    Course("英语", "王老师", [Room("102"), Room("103")])
]

rooms = [Room("101"), Room("102"), Room("103")]
times = [TimeSlot("9:00-10:00"), TimeSlot("10:00-11:00"), TimeSlot("11:00-12:00")]

# 调用回溯算法
if backtrack(courses, rooms, times):
    print("找到一个有效的课程表：")
    print_schedule(courses)
else:
    print("无法找到满足所有约束条件的课程表")
